package com.itheima;

import org.junit.Test;

import java.util.*;

public class ArraysProblem {

    public int[][] topic56(int[][] intervals) {
        int m = intervals.length;
        int n = intervals[0].length;

        List<int[]> list = new ArrayList<int[]>();

//        List<int[]> res = new ArrayList<>();
        Deque<int[]> stack = new LinkedList<>(); //stack
        for (int i = 0; i < m; i++) {

            list.add(intervals[i]);
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
            }
        });
        for(int i = 0; i < m; i++){
            if(!stack.isEmpty()){
                int[] top = stack.pop();
                if(top[1] >= list.get(i)[1]) {
                    stack.push(new int[]{top[0], top[1]});
                } else if(top[1] >= list.get(i)[0]){
                    stack.push(new int[]{top[0], list.get(i)[1]});
                } else {
                    stack.push(new int[]{top[0], top[1]});
                    stack.push(new int[]{list.get(i)[0], list.get(i)[1]});
                }
            } else {
                stack.push(new int[]{list.get(i)[0], list.get(i)[1]});
            }
        }


        return stack.toArray(new int[stack.size()][]);
    }

    public void topic189(int[] nums, int k) {
        int n = nums.length;

        int i = 0, j = n - 1;
        while (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++; j--;
        }
        i = 0; j = k - 1;
        while (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++; j--;
        }

        i = k; j = n - 1;
        while(i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++; j--;
        }
    }

    public int topic41(int[] nums) {
        Set<Integer> set = new HashSet();
        int max = 0;
        int res = 0;
        for(int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
            if(nums[i] > max) {
                max = nums[i];
            }
        }
        if(max == Integer.MAX_VALUE)
            max = Integer.MIN_VALUE - 1;
        for(int i = 1; i <= max + 1; i++) {
            if(!set.contains(i)) {
                res = i;
                break;
            }
        }
        return res;
    }


    public int[] topic238(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for(int i = 0; i < n; i++){
            ans[i] = 1;
        }
        int ln = 1, rn = 1;
        int l = 0, r = n - 1;
        while(l < n && r >= 0) {
            ans[r] *=  rn;
            ans[l] *=  ln;

            rn = rn * nums[r];

            ln = ln * nums[l];
            l++;
            r--;



        }

//        System.out.println(Arrays.toString(ans));
        return ans;
    }

    @Test
    public void test() {
        System.out.println(topic41(new int[]{1,2,3,10,2147483647,9}));
//        topic238(new int[]{1,2,3,4});
    }

}
